package jun;

import java.awt.*;

/**
 * @author ：冯涛滔
 * @date ：Created in 2020-6-11 15:10
 * @description：
 * @modified By：
 * @version:
 */
public class Jun11 {
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/longest-palindromic-subsequence/solution/516-zui-chang-hui-wen-zi-xu-lie-by-ming-zhi-shan-y/  516. 最长回文子序列
     * create time: 2020-6-11 15:29
     * @params [s]
     * @return int
     */
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] f = new int[n][n];
        for (int i = n - 1; i >= 0; i--) {
            f[i][i] = 1;
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    f[i][j] = f[i + 1][j - 1] + 2;
                } else {
                    f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);
                }
            }
        }
        return f[0][n - 1];
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/ 123. 买卖股票的最佳时机 III
     * create time: 2020-6-11 16:03
     * @params [prices]
     * @return int
     */
    public static int maxProfit(int[] prices) {
        if(prices.length==0){
            return 0;
        }
        //0没有交易 1第一次买入 2第二次买入
       int[][][] dp = new int[prices.length+1][3][2];
        //回来看下初始化怎么办
        dp[0][1][1] = -prices[0];
        dp[0][2][1] = -prices[0];
        for (int i = 1; i <= prices.length; i++) {
            dp[i][1][1] = Math.max(dp[i-1][1][1],-prices[i-1]);//第i天有一次买入交易持有股票 两种选择 上一天进行买入或者当天进行买入
            dp[i][1][0] = Math.max(dp[i-1][1][1]+prices[i-1],dp[i-1][1][0]);//第i天有一次买入但是没有持有股票 两种选择将上一天持有的股票卖掉 或者 保持上一天有一次买入但是也没持有股票
            dp[i][2][1] = Math.max(dp[i-1][2][1],dp[i-1][1][0]-prices[i-1]);//第i天有两次买入持有股票 两种选择 上一天有两次买入持有股票 或者上一天有一次买入并且没有持有股票买入当天的股票
            dp[i][2][0] = Math.max(dp[i-1][2][0],dp[i-1][2][1]+prices[i-1]);//第i天有两次买入记录并且没有持有股票 两种选择 上一天有两次买入记录并且没有持有股票 或者上一天 有两次买入记录持有股票当天卖出
        }
        return dp[prices.length][2][0];
    }
    public int maxProfit(int k, int[] prices) {
        if(prices.length==0){
            return 0;
        }
        //0没有交易 1第一次买入 2第二次买入
        int[][][] dp = new int[prices.length+1][k+1][2];
        //回来看下初始化怎么办
        dp[0][1][1] = -prices[0];
        dp[0][2][1] = -prices[0];
        for (int i = 1; i <= prices.length; i++) {
            for (int j = 1; j < k; j++) {
                dp[i][j][1] = Math.max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i-1]);//第i天有两次买入持有股票 两种选择 上一天有两次买入持有股票 或者上一天有一次买入并且没有持有股票买入当天的股票
                dp[i][j][0] = Math.max(dp[i-1][j][0],dp[i-1][j][1]+prices[i-1]);
            }
        }
        return dp[prices.length][k][0];
    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/ 121. 买卖股票的最佳时机 dp表版
     * create time: 2020-6-11 16:34
     * @params [prices]
     * @return int
     */
    public static int maxProfit2(int[] prices) {
       int[][] dp = new int[prices.length+1][2];
        dp[0][1] = -prices[0];
        for (int i = 1; i <= prices.length; i++) {
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i-1]);//今天没有股票
            dp[i][1] = Math.max(dp[i-1][1],-prices[i]);//今天有股票
        }
        return dp[prices.length][0];

    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/ 122. 买卖股票的最佳时机 II
     * create time: 2020-6-11 17:09
     * @params [prices]
     * @return int
     */
    public static int maxProfit3(int[] prices) {
        if(prices.length==0){
            return 0;
        }
        int[][] dp = new int[prices.length+1][2];
        dp[0][1] = -prices[0];
        for (int i = 1; i <= prices.length; i++) {
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i-1]);//今天没有股票
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i-1]);//今天有股票
        }
        return dp[prices.length][0];

    }
    public static void main(String[] args) {
        Color c = new Color(200,150,255);
        Frame f= new Frame("aa");
        f.setLayout(new BorderLayout());
        f.setBackground(c);
        f.setSize(300,300);
        f.setLocation(300,200);
        f.add("East",new Button("aa"));
        f.add("South",new Button("aa"));
        f.add("West",new Button("aa"));
        f.add("Center",new Button("aa"));
        f.add("North",new Button("aa"));
        f.setVisible(true);


    }
}
